This invention relates to the field of interleaving data bits and is particularly applicable to interleavers used in mobile telecommunications devices.
It is common in telecommunications systems for data to be interleaved prior to transmission in order to minimise the effect of burst errors on the data, thus increasing the probability that the data can be decoded when it is received. In a simple example, if the data to be transmitted comprises four eight-bit words, an interleaved data block may be generated by using the first bit of the first word as the first bit of the interleaved data block, with the first bit of the second word being used as the second bit of the interleaved data block, the first bit of the third word being used as the third bit of the interleaved data block and the first bit of the fourth word being used as the fourth bit of the interleaved data block. The second bit of the first word may then be used as the fifth bit of the interleaved data block, and so on, until a thirty-two bit interleaved data block has been generated. In this way, adjacent bits of the data to be transmitted do not appear adjacent to each other in the interleaved data block. Thus, in the event of a burst error which renders several successive bits of the transmitted interleaved data block unintelligible, it is possible that the transmitted data can still be recovered, as after de-interleaving the unintelligible bits are dispersed throughout the data block, and thus no individual word of the transmitted data has an extended sequence of unintelligible bits, which would prevent successful decoding of that word.
In certain newer telecommunications systems, such as the Long Term Evolution (LTE) of the Third Generation Partnership Program (3GPP) there is a requirement for transmitters and receivers to support high data throughput rates. This has placed strain on functional blocks, such as turbo decoders, which are used to perform channel decoding.
One method of improving data throughput rates is to use a plurality (typically two, four, eight or sixteen) of parallel processing engines to perform decoding operations within a turbo decoder, each of which processes a different subset of a sequence to be decoded. Interleaving (and de-interleaving) are used when passing sequences back and forth between constituent decoders within a turbo decoder.
Another method of improving the data throughput of a turbo decoder is to arrange its interleaving process to output multiple interleaved bits at a time (and to arrange, likewise, its de-interleaving process to output multiple de-interleaved bits at a time). Thus, simple bitwise interleaving and de-interleaving, as described above, are not employed.
In a typical turbo decoder de-interleaver, an interleaved data block of size k bits is written to memory in input words of p bits in length, and de-interleaved output words of s bits in length are extracted from the data block (where k, p, and s have integer values). The data block of size k can be considered as a two-dimensional array containing a plurality of rows and columns of bits, with the input words of length p bits being written to columns of the data block and the output words of length s bits being created from words constituted by rows read from the data block. In reality however, the data block is a one-dimensional sequence from which bits are read to form a de-interleaved output word.
A number of difficulties arise with such systems. Where the process of de-interleaving is carried out in an application specific integrated circuit (ASIC), programmable logic device (PLD), field programmable gate array (FPGA) or similar device, such a system gives rise to inefficient use of the limited on-chip memory resources of the device, as the data block containing data to be de-interleaved may occupy the resources of an entire memory block of the device, which memory block may have far more capacity than is required to store the data block. Additionally, systems of this type are limited in their speed of throughput, as it typically takes a number of clock cycles to generate a complete de-interleaved data word of the desired number of bits s. Also, to ensure that the bits which make up the de-interleaved data word are selected in the correct order, look up tables may be employed, which may occupy a large amount of memory. In the example of 3GPP LTE turbo decoding, there, are 288 different values for k, ranging from 40 to 6144, and p may be 1, 2, 4, 8 or 16. Thus it will be appreciated that even if the value of s is fixed at 8, there are a large number of de-interleaving patterns that must be stored in look up tables.